【题解】 [CQOI2011]动态逆序对 CDQ分治 luoguP3157 | Qiuly's blog!

【题解】 [CQOI2011]动态逆序对 CDQ分治 luoguP3157

Posted on | In | Comments:

一个可爱的 $CDQ$ ，我们将原始序列看成一个一个加入，然后后面的操作就是一个一个删除，这么一个一个操作我们都记下来，然后每个操作记一个 $id$ 表示它将为第几个时间点做出贡献。

当然对于原始序列的一个一个插入的操作这里的贡献是 $1$ ，删除操作的贡献自然是 $-1$ 。

每个时间点统计答案，最后输出前做一个前缀和然后依次输出就好了。

这是具体的框架，但是统计 $ans$ 数组具体怎么做呢？

可以知道对于一个位置 $i$ ，位置上的元素是 $a_i$ 。对于一个 $j$ 满足 $j\leq i$ ，并且 $a_i\leq a_j$ ，而且还要保证 $id_j\leq id_i$ ，那么 $j$ 就可以对 $i$ 做出贡献。这个就是在 $i$ 前面的元素可以做出的贡献。$i$ 后面的元素做出的贡献同理。

这就是一个很普通的三位偏序了，注意要开 $long\ long$ 。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+2;
template <typename _Tp> inline void IN(_Tp &x){
    x=0;int flag=0;char ch;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

int n,m,cnt,pos[N],a[N];
long long ans[N];
struct Query{int r,v,d,id;}Q[N];
bool cmp(Query a,Query b) {return a.d<b.d;}

int C[N];
#define lowbit(x) ((x)&(-(x)))
void add(int x,int v) {for(;x<=n;x+=lowbit(x))C[x]+=v;}
int sum(int x) {int res=0;for(;x;x-=lowbit(x))res+=C[x];return res;}

inline void CDQ(int l,int r) {
    if(l==r)return;
    int mid=(l+r)>>1;
    CDQ(l,mid),CDQ(mid+1,r);
    sort(Q+l,Q+mid+1,cmp),sort(Q+mid+1,Q+r+1,cmp);
    int j=l;
    for(int i=mid+1;i<=r;++i) {
        while(j<=mid&&Q[j].d<=Q[i].d) add(Q[j].v,Q[j].r),++j;
        ans[Q[i].id]+=Q[i].r*(sum(n)-sum(Q[i].v));
    }
    for(int i=l;i<j;++i) add(Q[i].v,-Q[i].r);
    j=mid;
    for(int i=r;i>mid;--i) {
        while(j>=l&&Q[j].d>=Q[i].d) add(Q[j].v,Q[j].r),--j;
        ans[Q[i].id]+=Q[i].r*sum(Q[i].v-1);
    }
    for(int i=mid;i>j;--i) add(Q[i].v,-Q[i].r);
}

int main(){
    IN(n),IN(m);
    for(int i=1;i<=n;++i)
        IN(a[i]),pos[a[i]]=i,Q[++cnt]=(Query){1,a[i],i,0};
    for(int i=1;i<=m;++i) {
        int x;IN(x);
        Q[++cnt]=(Query){-1,x,pos[x],i};
    }
    CDQ(1,cnt);
    for(int i=1;i<=m;++i) ans[i]+=ans[i-1];
    for(int i=0;i<m;++i) printf("%lld\n",ans[i]);
    return 0;
}

本文标题:【题解】 [CQOI2011]动态逆序对 CDQ分治 luoguP3157

文章作者:Qiuly

发布时间:2019年03月30日 - 00:00

最后更新:2019年03月30日 - 15:37

原始链接:http://qiulyblog.github.io/2019/03/30/[题解]luoguP3157/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。